1. Field of the Invention
The present invention generally relates to a method and apparatus for constructing autonomic advisors, and more particularly to a method and apparatus for constructing computer-executable procedures using scored sequences of examples.
2. Description of the Related Art
Consider the problem of automatically constructing a model of a procedure using sequences of examples.
For purposes of the present application, the term “procedure” refers to a structured task having a definable goal, and that can be automated to a point where the required user intervention or input is limited. Examples of procedures include installing an application on a computer system, managing payroll, troubleshooting a network card, driving a car while following directions, etc.
Activities such as writing a novel or preparing a patent application are not procedures in the sense of this patent because the intrinsic variability of the task requires too many user decisions to be effectively automated. One of ordinary skill in the art would recognize the difference between this definition of “procedure” and the definition of “procedure” commonly used in the Computer Science field, where the term is synonymous of “routine”, “subroutine”, and sometimes “function”, namely, a section of a program that performs a specific task (without necessarily returning a result).
For purposes of the present application, the term “model” refers to an executable description of the procedure, namely, to an entity that can provide a human-readable description of the procedure and that can be automatically executed on behalf of or in cooperation with the user.
There are two main approaches to constructing executable models: programming, and induction from examples.
Programming tools exist to automate specific types of procedures: for example, the Microsoft® Windows® Installer SDK provides tools for automating the installation of application programs on computers running the Microsoft® Windows® operating systems. Similarly, workflow management systems are tools that facilitate the automation of business processes (or “workflows”). Finally, tools from Artificial Intelligence, such as Expert Systems (e.g., see Peter Jackson, Introduction to Expert Systems, Addison Wesley, 2004), can be manually programmed to produce a model of the task.
A second main approach is programming by example (e.g., as disclosed by Henry Lieberman, Your Wish is My Command: Programming by Example, Morgan Kaufmann, 2001), also known as programming by demonstration (PBD).
A PBD system is an inference engine that takes as input a set of input-output pairs describing the desired behavior of a program, and produces a program whose behavior is consistent with the set of input-output pairs. PBD has been adapted to capturing procedural knowledge, as taught, for example, by Lau, et al. (e.g., see Tessa Lau, Pedro Domingos, and Daniel S. Weld, “Learning programs from traces using version space algebra,” in Proc. Intern. Conf. on Knowledge capture, pp. 36-43, 2003), by constructing PBD systems that produce programs from a set of sequences of input-output pairs.
Here, each sequence of input-output pairs describes an execution of a procedure by a user. Since the model produced by the system is a model of the procedure from the viewpoint of the user, each input-output pair in a sequence describes a specific interaction between the user and the applications used to perform the procedure.
More specifically, the input in the input-output pair is a description of what the user sees on the screen and the output is a description of the user action.
The methods taught by Lau, et al., and by Lieberman have one of several limitations including that they require the user to make correspondences between analogous steps in different sequences, or they can learn from individual sequences.
Co-pending U.S. patent application Ser. No. 10/729,736, by Daniel Oblinger, Vittorio Castelli, Tessa Lau, and Lawrence Bergman, entitled “Alignment and generalization of demonstrated procedure traces”) teaches a method for capturing procedural knowledge by demonstration from multiple sequences of input-output pairs by simultaneous alignment and generalization of the demonstrated traces.
Co-pending U.S. patent application Ser. No. 10/972,028, by Daniel Oblinger, Vittorio Castelli, Tessa Lau, and Lawrence Bergman, entitled “Method for Inducing a Hidden Markov Model Learning With A Similarity Metric”, teaches a method for improving the efficiency of inducing Hidden Markov Models (e.g., see Y. Bengio and P. Frasconi, “Input-Output HMM's for Sequence Processing,” IEEE Trans. Neural Networks, 7(5):1231-1249, September 1996).
Hidden Markov Models can be used as the induction engine in an embodiment of the above mentioned U.S. patent application Ser. No. 10/729,736, Daniel Oblinger, Vittorio Castelli, Tessa Lau, and Lawrence Bergman, “Alignment and generalization of demonstrated procedure traces”.
Finally, other tools from Artificial Intelligence, such as Bayesian Networks (e.g., see David Heckerman, “A tutorial on learning Bayesian Networks”, Microsoft Technical Report MSR-TR-95-06, 1995), can be manually built by identifying relevant parameters and variables of the task, and automatically inducing the relations between said parameters from examples or manually constructing said relations.
Unlike the PBD approach, the skeleton of the model is manually constructed, and from the viewpoint of the current patent application, these tools are considered in the same category of programming tools.
Procedure models can be constructed for different application areas. Co-pending U.S. patent application Ser. No. 10/630,959, by Tessa Lau, Vittorio Castelli, Lawrence Bergman, and Daniel Oblinger, entitled “Systems and methods for generating and distributing executable procedures for technical desk-side support” teaches how to construct procedure models using PBD techniques for deskside support.
Procedure models can be used to guide, assist, or replace a user in repetitive tasks involving a single application, as taught in the above-mentioned Tessa Lau, et al., or multiple applications.
Procedure models can also be used for automation purposes, for example in robotic tasks where the robot can learn from previous experience, in control systems for plants, and in autonomic computing as described in IBM System Journal, issue on Autonomic Computing, vol. 42, nr. 1, 2003, available at http://researchweb.watson.ibm.com/journal/sj42-1.html where computer systems are self-regulating thanks to a variety of hardware and software mechanisms.
The software mechanisms, henceforth referred to as “autonomic agents”, perform tasks related to self-regulation, self-optimization, self-healing, and self-protection of the computer systems.
According to the present definition, autonomic agents actually perform procedures. Due to the complexity of computer systems, effective autonomic agents can be difficult to build using traditional programming techniques; learning behavior from previous experience is likely a necessary component to the construction of such agents.
Traditional techniques for learning procedural knowledge from demonstration, taught in the above-mentioned conventional methods, can be divided into two broad categories: approaches that produce deterministic models of a procedure, and approaches that produce probabilistic models of a procedure. In general, one having ordinary skill in the art would appreciate that probabilistic models subsume deterministic models as a special case.
All the methods for learning procedural knowledge from demonstrations taught in the art assume that the examples provided by the user are “good” examples, namely, examples of successful executions of the procedure.
Specific uses of both positive and negative examples are taught, for example, in Robert C. Miller and Brad A. Myers. “LAPIS: Smart Editing With Text Structure.” Extended abstract for CHI 2002 formal demonstration, Minneapolis, Minn., April 2002, where they are used to learn patterns, in Tessa A. Lau and Daniel S. Weld, “Programming by Demonstration, And Inductive Learning Formulation”, Proc 1999 ACM Int. Conf. Intelligent User Interfaces, where they are used to operate on version spaces (namely, to refine a set of hypotheses or to enlarge a set of hypotheses), and in Maulsby D. and Witten I. H, “Learning agents: from user study to implementation,” IEEE Computer 30(11), pp 36-44, 1997, where positive examples are predictions of the system that the user accepts, and negative examples are predictions of the system that the user rejects, and positive and negative examples are used to interactively induce individual predictive steps. One of ordinary skill in the art would appreciate the similarity of the approaches taught in Robert C. Miller and Brad A. Myers. “LAPIS: Smart Editing With Text Structure.” Extended abstract for CHI 2002 formal demonstration, Minneapolis, Minn., April 2002 and Tessa A. Lau and Daniel S. Weld, “Programming by Demonstration, And Inductive Learning Formulation”, Proc 1999 ACM Int. Conf. Intelligent User Interfaces.
A limitation of the conventional approaches is the use of positive and negative examples to induce individual steps of the procedure.
The conventional methods are limited to positive, or to positive and negative examples. In general, the distinction between positive and negative examples is not sufficient.
As an illustrative example, consider the case of an expert performing an action (or a sequence of actions) during a system administration procedure, for example aimed at reducing the response time of an on-line computer system. Here, it would be possible to measure the effectiveness of the system administrator action, for example, in terms of reduction of response time. Different actions have in general different effects and result in different reductions of response time (and potentially, in an increase in response time).
A distinction between positive and negative actions based on whether actions decrease or increase the response time is clearly too coarse to be useful: an action A that slightly reduces the response time is labeled as “positive”, while an action B that slightly increases the response time is labeled as “negative”, although it is essentially equivalent to action A. More disturbingly, an action C that substantially reduces the response time is labeled “positive” just like action A, although C is clearly to be preferred.
In general, there is a need for a method for learning procedural knowledge from scored demonstrations, where individual steps, subsequences, and sequences have associated scores.
Finally, consider the case of an autonomic agent that implements a policy (e.g., that tries to match a set of requirements). Depending on the desired policy, one would score differently the same sequence of input-output pairs.
The conventional methods to induce an autonomic agent for a specific policy consist of providing a collection of positive and potentially negative examples for the policy. This process is onerous and expensive.
Thus, hitherto the present invention, there has been no efficient and effective approach, which would allow a user to provide a scoring function adapted to the specific policy, score existing recorded sequences of input-output pairs, and induce an agent from the scored sequences.
Hence, the conventional methods have not been able to reuse existing sequences to infer new policies, thus reducing the need for new sets of examples to be used in the inference.
Additionally, the conventional methods have not been adaptive. That is, the agent has not been able to learn from its own experience and thus the agent has not been able to score its actions by using the scoring function, and then update its model of the procedure accordingly.